package leetcode.动态规划和贪心;

/**
 * 跳跃游戏
 *
 * 贪婪算法：总是做出当前的最优解
 */
public class Test55跳跃游戏 {

    public static boolean canJump(int[] nums) {
        if (nums.length == 0 || nums.length == 1)
            return true;
        // 某一元素值可以跳跃的最大长度
        int max = 0;
        for (int i = 0; i < nums.length; i++) {

            /**
             * 当遇到元素值为0的时候，max会原地踏步，无法跳出，但是i是在一直累加的
             *      正常情况下，只需要几次（小于i）跳跃就可以出去，但是遇到max踏步的时候
             *      i就会超越max，此时就是无法跳跃到最后的情况了，返回false。
             *
             *
             *      其实max踏步是一件巧合的事，因为上一次最远的跳跃必须跳到值为0的元素上
             *
             */
            if (i > max) {
                return false;
            }
            //贪心法：求解可以到达的最远步数
            max = Math.max(nums[i] + i, max);
            // 为什么是nums[i] + i：当前值 + 当前下标 = 最远可以到达的距离
        }
        return true;
    }

    public static void main(String[] args) {
//        int[] nums = {2,3,1,1,4};
//        int[] nums = {3,2,1,0,4};
        int[] nums = {2,0,0};
        System.out.println(canJump(nums));
    }
}
